package com.zwj.interview.二分查找;

/**
 * @Author: Zwj
 * @Date: 2022/3/1 15:54
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 */
public class 接雨水 {

    /**
     * @param height
     * @return 对于每个位置i，最多能装下的水为：
     * water[i]=min(
     * 左边最高的柱子
     * max(height[0..i]),
     * 右边最高的柱子
     * max(height[i..n-1)
     * )-height[i]
     */
    public int trap(int[] height) {
        int ans = 0;
        if (height.length == 0) {
            return 0;
        }
        int n = height.length;
        //申请两个数组，l_max[i]表示height[0..i]中的最大值
        int[] l_max = new int[height.length];
        //r_max[i]表示height[i..n-1]中的最大值
        int[] r_max = new int[height.length];
        //边界
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        //从左往右计算l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(l_max[i - 1], height[i]);
        }
        //从右往左计算r_max
        for (int i = n - 2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i + 1]);
        }
        //计算答案
        for (int i = 1; i < n - 1; i++) {
            ans += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return ans;
    }




}